package algorithm.kmp;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

import java.util.Arrays;

/**
 * KMP是一种字符串查找算法  https://www.cnblogs.com/zzuuoo666/p/9028287.html
 */
public class KMPDemo {
    public static void main(String[] args) {
        String data = "Hello Woorld!";
        System.out.println(data.indexOf("He"));
        System.out.println("暴力匹配: " + violentMatch(data, "or"));
        StringBuilder stringBuilder = new StringBuilder(data);
        System.out.println(stringBuilder.reverse().toString());

        int[] next = kmpNext("ABABCDABAAB");
        System.out.println(Arrays.toString(next));
        System.out.println(kmpSearch("BBC ABCDAB ABCDABCDABDE", "ABCDABD", next));
        System.out.println("-----------");
        System.out.println(Arrays.toString(kmpNext("ABABCABAA")));

    }


    /**
     * kmp算法查找字符串
     * @param str1 源字符串
     * @param str2 子串
     * @param next 子串的匹配表
     * @return index
     */
    private static int kmpSearch(String str1, String str2, int[] next) {
        for (int i = 0, j = 0; i < str1.length(); i++) {
            while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
                j = next[j - 1];
            }
            System.out.println(j);
            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
            }
            if (j == str2.length()) {
                return i - j + 1;
            }
        }
        return -1;
    }


    /**
     * 获取字符串的匹配表
     * @param dest
     * @return
     */
    private static int[] kmpNext(String dest) {
        int[] next = new int[dest.length()];
        next[0] = 0;
        for (int i = 1, j = 0; i < dest.length(); i++) {
            // 当 dest.charAt(i) != dest.charAt(j),我们需要从 next[j - 1]重新获取新的j
            // 直到我们发现有 dest.charAt(i) == dest.charAt(j) 成立才退出
            // 这是kmp算法的核心！！！  完全理解不了！！！
            while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
                j = next[j - 1];
            }
            if (dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }


    /**
     * 暴力匹配(最好别用...)
     *
     * @param data1 数组1
     * @param data2 数组2
     * @return 数组2第一次出现在数组1的位置
     */
    private static int violentMatch(String data1, String data2) {
        byte[] data1Bytes = data1.getBytes();
        byte[] data2Bytes = data2.getBytes();

        int j = 0;
        for (int i = 0; i < data1Bytes.length; i++) {
            if (data1Bytes[i]  == data2Bytes[j]) {
                j++;
            } else {
                // 这句话很重要  主要就是解决一端数据匹配不成功之后要返回要原来的位置重新开始匹配..
                // 所以此处会有类似于回溯的问题  有点耽误时间，所以引出了KMP算法
                i = i - j;
                j = 0;
            }
            if (data2Bytes.length == j) {
                return i + 1 - j;
            }
        }

        return -1;
    }
}
